\section{Preliminaries}\label{s:prel}

Throughout the paper we consider the following approval-based multiwinner election instance. 
We are given a bipartite approval graph $G=(N\cup C, E)$ where $N$ is a finite set of voters and $C$ is a finite set of candidates. 
We are additionally given a vector $s\in\R^N$ of vote strengths, where $s_n$ is the strength of $n$'s vote, and a target number $k$ of candidates to elect, where $0< k<|C|$.
For each voter $n\in N$, $C_n:=\{c\in C: \ nc\in E\}$ represents her approval ballot, i.e., the subset of candidates that $n$ approves of, and for each candidate $c\in C$ we denote by $N_c:=\{n\in N: \ nc\in E\}$ the set of voters approving $c$, where $nc$ is shorthand for edge $\{n,c\}$. 
To avoid trivialities, we assume that the input graph $G$ has no isolated vertices. 
For any $c\in C\setminus A$, we write $A+c$ and $A-c$ as shorthands for $A\cup\{c\}$ and $A\setminus \{c\}$ respectively. 

\paragraph{Proportional justified representation (PJR).} 
The PJR property was introduced in~\cite{sanchez2017proportional} for voters with unit vote strength. We present its natural generalization to positive real valued strengths. 
A committee $A\subseteq C$ of $k$ members satisfies PJR if, for any group $N'\subseteq N$ of voters and any integer $0<r\leq k$, we have that 
\begin{itemize}
\item[a)] if $|\cap_{n\in N'} C_n|\geq r$
\item[b)] and $\sum_{n\in N'} s_n \geq r\cdot \hat{t}$, 
\item[c)] then $|A\cap (\cup_{n\in N'} C_n)|\geq r$,
\end{itemize}
%
where $\hat{t}:=\sum_{n\in N} s_n / k$. 
In words, if there is a group $N'$ of voters with at least $r$ commonly approved candidates, and enough aggregate vote strength to provide each of these candidates with a vote support of at least $\hat{t}$, then this group has a justified right to be represented by $r$ members in committee $A$, though not necessarily commonly approved. 
This right is justified because $\hat{t}$ is the largest possible average vote support that the full voter set $N$ can provide to any committee of $k$ members. 

\paragraph{Maximin support objective.} 
For the given instance, we consider a solution consisting of a tuple $(A,w)$, where $A\subseteq C$ is a committee of $k$ candidates, and $w\in\R^E$ is a vector of non-negative edge weights that represents a fractional distribution of each voter's vote among her approved candidates.%
\footnote{This edge weight vector is related to the notions of \emph{support distribution function} in~\cite{sanchez2016maximin} and \emph{price system} in~\cite{peters2019proportionality}. In particular, all election rules considered in this paper are \emph{priceable}, as defined in~\cite{peters2019proportionality}.} 
For instance, for a voter $n$ this distribution may assign a third of $s_n$ to $c_1$ and two thirds of $s_n$ to $c_2$, where $c_1, c_2\in C_n$.
Vector $w$ is \emph{feasible}%
\footnote{Intuitively, a feasible solution $(A,w)$ should also observe $w_{nc}=0$ for each edge $nc$ with $c\not\in A$. 
However, as this constraint can easily be enforced in post-computation, we ignore it so that the feasibility of a vector $w$ is independent of any committee.} 
if  % 
%
\begin{equation}
    \sum_{c\in C_n} w_{nc}\leq s_n \quad \text{ for each voter } n\in N. \label{eq:feasible}
\end{equation}

In our analyses, we will also consider \emph{partial} committees, with $|A|\leq k$. If $|A|=k$, we call it \emph{full}. 
All solutions $(A,w)$ in this paper are assumed to be feasible and full unless stated otherwise. 
Given a (possibly partial, unfeasible) solution $(A,w)$, we define the \emph{support} over the committee members as 
\begin{align}
\supp_w(c) &:=\sum_{n\in N_c} w_{nc} \quad \text{for each $c\in A, \quad$ and } \nonumber \\
\supp_w(A)& :=\min_{c\in A} \supp_w(c), \label{eq:support}
\end{align}
with the convention that $\supp_w(\emptyset)=\infty$ for any weight vector $w\in\R^E$. 
The maximin support objective, introduced in~\cite{sanchez2016maximin}, asks to maximize the least member support $\supp_w(A)$ over all feasible full solutions $(A,w)$. 

\paragraph{Balanced solutions.}
For a fixed committee $A$, a feasible weight vector $w\in\R^E$ that maximizes $\supp_w(A)$ can be found efficiently. 
However, we seek additional desirable properties for a weight vector which can still be achieved efficiently. We say that a feasible $w\in\R^E$ is \emph{balanced for $A$}, or that $(A,w)$ is a balanced solution, if
\begin{enumerate}
    \item it maximizes the sum of member supports, $\sum_{c\in A} \supp_w(c)$, over all feasible weight vectors, and 
    \item it minimizes the sum of supports squared, $\sum_{c\in A} \supp_w^2(c)$, over all vectors that observe the first property above. 
\end{enumerate}
%
In other words, a balanced weight vector maximizes the sum of supports and then minimizes their variance. 
In the next lemma, whose proof is delayed to Appendix~\ref{s:proofs}, we establish some key properties that we exploit in our analyses. 

\begin{lemma}\label{lem:balanced}
Let $(A,w)$ be a balanced, possibly partial solution. Then,
\begin{enumerate}
    \item vector $w$ simultaneously maximizes, for each $1\leq r \leq |A|$, the quantity $\min_{A'\subseteq A, |A'|=r} \ \sum_{c\in A'} \supp_{w'}(c)$ over all feasible weight vectors $w'\in\R^E$; 
		\item for each $n\in N$, $\sum_{c\in A\cap C_n} w_{nc}=s_n$ if $A\cap C_n\neq \emptyset$; and
    \item for each $n\in N$ and each candidate $c\in A\cap C_n$, if $w_{nc} > 0$ then $\supp_w(c)=\supp_w(A\cap C_n)$. 
\end{enumerate}
Furthermore, a feasible solution $(A,w)$ is balanced if and only if it observes properties 2 and 3 above, which can be tested in $O(|E|)$ time.
\end{lemma}

Notice that by setting $r=1$ in the first property, we obtain that balanced vector $w$ indeed maximizes the least member support $\supp_w(A)$ over all feasible weight vectors. 
More generally, for each threshold $r$ the quantity defined in the first property defines a lower bound on the cost for an adversary to get $r$ representatives in the validator committee in NPoS, so maximizing these objectives simultaneously for all thresholds $r$ aligns with our security objective as it makes any attack as costly as possible. 
The second point follows from the fact that the sum of member supports is maximal, so all the available vote strength must be distributed among candidates in $A$. 
The third point is a consequence of having the supports as evenly distributed as possible within $A$: for each voter $n$, all of its vote strength should be assigned exclusively to the candidates in $A\cap C_n$ with least support $\supp_w(A\cap C_n)$. 

In Appendix~\ref{s:balanced} we present algorithms for computing a balanced weight vector for a given committee $A$. 
In particular, we prove that one can be found in time $O(|E|\cdot k + k^3)$ using parametric flow techniques, which to the best of our knowledge is the fastest algorithm in the literature even for the problem of maximizing $\supp_w(A)$.

\begin{remark}\label{rem:bal}
In the remainder of the paper, we denote by $\bal$ the time complexity of finding a balanced weight vector for a given (possibly partial) committee, depending on the precise algorithm used.
\end{remark}

\begin{remark}
In all algorithms analyzed, we assume that all numerical operations take constant time.
\end{remark}
